In signal processing, median filtering provides a nonlinear signal smoothing operation which may be used for noise reduction. In data processing, median filtering is used for smoothing and related data analysis tasks. Median filtering is characterized in its ability to smooth a data sequence, thereby reducing or eliminating noise, while preserving discontinuities in the data sequence. The preservation of discontinuities or other sharp changes in a data sequence presents an advantage over linear filters, such as linear low-pass filters, which tend to smooth out such changes. Median filtering is, therefore, useful in applications such as sensor reading. For example, a median filter applied to the readings from a current sensor may remove or reduce noise in the current readings, but still be able to quickly and effectively detect overcurrent conditions associated with a current transient or similar event.
Median filtering requires the sorting of input data samples into an ordered or partially-ordered sequence. Hardware implementations of median filters typically use a sorting network based upon multiple stages of comparators, wherein each stage includes multiple comparators. In an asynchronous implementation of such a sorting network, each stage of comparators directly couples to and feeds the next stage of comparators. In a pipelined (synchronous) implementation of such a sorting network, the comparator stages are separated by registers that latch the comparator outputs from each stage, in order to feed the comparator inputs of the subsequent stage. Regardless of whether the sorting network uses an asynchronous or pipelined (synchronous) circuit, such sorting networks require multiple stages wherein each stage includes multiple comparators.
Consider a sorting network, which may be part of a median filter or not, operating over w samples of an input data sequence, wherein w represents a window size and is a multiple of 2 such that w=2p. As explained in R. Mueller et al., “Sorting networks on FPGAs,” The VLDB Journal, February 2012, Volume 21, Issue 1, pp 1-23, an even-odd merging network may be used to implement such a sorting network and uses S stages and C comparators, wherein:
                                          C            ⁡                          (                              2                p                            )                                =                                                    (                                                      p                    2                                    -                  p                  +                  4                                )                            ⁢                              2                                  (                                      p                    -                    2                                    )                                                      -            1                          ,                            (        1        )                                          S          ⁡                      (                          2              p                        )                          =                                            p              ⁡                              (                                  p                  +                  1                                )                                      2                    .                                    (        2        )            A median filter operating over an even number of input samples, as given by w=2p, may not require the complete sorting of the input data into a monotonically increasing (or decreasing) sequence, as the median filter might only require the identification of the two input data values in the middle of a sorted sequence. In other words, the comparative ordering of these two values may not be needed. By taking advantage of this, a median filter may use a sorting network having one fewer stages than given in equation (2), and p fewer comparators than given in equation (1).
The comparators make up a significant portion, and often a majority, of the die area required in a hardware implementation of a sorting network or a median filter that includes such a sorting network. Table 1 provides the number of stages and comparators that are required by an even-odd merging network that performs a complete sorting of an input sequence having a window size of w, as calculated using equations (1) and (2). Also shown are the number of stages and the number of comparators required by a median filter that is able to omit the last stage of the complete sorting.
TABLE 1Required number of stages and numberof comparators for a sorting networkMedian filter withWindowComplete sortingincomplete sortingsize wp = log2(w)StagesComparatorsStagesComparators423513836192161641063359325151914186In addition to the comparators consuming a large amount of die area for any even-odd merging network, equation (1) and Table 1 show that the number of comparators increases exponentially as the input window size increases.
To quickly sort or filter input data and to minimize power consumption, hardware implementations of sorting networks and median filters are often preferred. This is particularly true when processing large amounts of input data, or when input data is being generated, and must be processed, at a high rate. However, the number of comparators required by such hardware implementations may lead to die area requirements that are unacceptably large for some applications, and may even make median filtering unfeasible for some applications. Such applications may opt for linear filters and their associated inferior performance, rather than incurring the cost and die size associated with median filtering.